/**
 * 
 */
package it.uniroma3.dia.digraph.algorithm.utility.convexhull;





/**
 * 
 * grahamScan implements the Graham Scan convex hull algorithm.  Given
 * a vector containing points it will return a vector of points forming
 * the convex hull of the input.  This class relies on extensions to the
 * point class called NewPoints.  grahamScan does not begin computing the
 * convex hull until three points have been provided.
 * @author Mark F. Hulber, May 1996. Adapted by Vincenzo Roselli
 *
 */

public class GrahamScan {

java.util.Vector<NewPoint> lines = new java.util.Vector<NewPoint>(100, 100);
java.util.Stack<NewPoint> stk = new java.util.Stack<NewPoint>();
java.util.Vector<NewPoint> s = new java.util.Vector<NewPoint>(100, 100);



/**
 * @param points
 * @return
 */
@SuppressWarnings("unchecked")
public java.util.Vector<NewPoint> doGraham(java.util.Vector<NewPoint> points) {

  int m = 0; 
  NewPoint temp, temp2;
  int n = points.size();
  int i;
  if (n > 2) {
     s.removeAllElements();
     s = (java.util.Vector<NewPoint>)points.clone();
     for (i = 1; i < n; i++)
        if (s.elementAt(i).y < s.elementAt(m).y || 
           ((s.elementAt(i).y == s.elementAt(m).y)&&
           (s.elementAt(i).x < s.elementAt(m).x)))
         m = i;
     temp = s.elementAt(0);
     s.setElementAt(s.elementAt(m),0);
     s.setElementAt(temp, m);
     
   // stage 2
     temp2 = s.elementAt(0);
	for (i = 2; i < n; i++) {
	  for (int j = n-1; j >= i; j --) {
	    if (temp2.polarCmp(s.elementAt(j-1), 
                            s.elementAt(j)) == 1) {
            temp = s.elementAt(j-1);
            s.setElementAt(s.elementAt(j),j-1);
            s.setElementAt(temp, j);
	    }
	  }
	}
     for (i = 1; s.elementAt(i+1).classify(
                               s.elementAt(0),
                               s.elementAt(i)) == 3; i++); 
     stk.removeAllElements();
     stk.push(s.elementAt(0));
     stk.push(s.elementAt(i));
            
     boolean blah;
	for (i = i+1; i < n; i++) {
       blah = true;
	  while ( blah ) {
          temp2 = stk.pop();
          if (s.elementAt(i).classify(stk.peek(),
                                                  temp2) == 0) {
             stk.push(temp2);
             blah = false;
	     }
	  }
       stk.push(s.elementAt(i));
	}

    lines.removeAllElements();

    while (!stk.empty())
       lines.addElement(stk.pop());
    return lines;
  }
  return null;
}
}